Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Consider the grammar with non-terminals N = {...
Start Learning for Free
Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:
S --> iCtSS1|a
S1 --> eS|ϵ
C --> b
S1 --> eS|ϵ
C --> b
The grammar is NOT LL(1) because:
- a)it is left recursive
- b)it is right recursive
- c)it is ambiguous
- d)It is not context-free
Correct answer is option 'C'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,...
A LL(1) grammar doesn't give to multiple entries in a single cell of its parsing table. It has only single entry in a single cell, hence it should be unambiguous.
Option A is wrong. Grammar is not left recursive. For a grammar to be left recursive a production should be of form A->Ab, where A is a single Non-Terminal and b is any string of grammar symbols.
Option B is wrong. Because a right recursive grammar has nothing to do with LL(1).
Option D is wrong. Because the given grammar is clearly a Context Free Grammar. A grammar is CFG if it has productions of the form A->(V∪T)* , where A is a single non-terminal and V is a set of Non-terminals and T is a set of Terminals.
Hence Option C should be the correct one. i.e. the grammar is ambiguous.
But let's see how the grammar is ambiguous.
If the grammar is ambiguous then it should give multiple entry in a cell while making its parsing table. And Parse table is made with the aid of two functions : FIRST and FOLLOW.
A parsing table of a grammar will not have multiple entries in a cell( i.e. will be a LL(1) grammar) if and only if the following conditions hold for each production of the form A->α|β 1) FIRST(α) ∩ FIRST(β) = Φ2) if FIRST(α) contains ' ε ' then FIRST(α) ∩ FOLLOW (A) = Φ and vice-versa.
Now,
- For the production , S->iCtSS1|a, rule 1 is satisfied, because FIRST(iCtSS1) ∩ FIRST(a) = {i} ∩ {a} = Φ
- For the production, S1->eS|ε, rule 1 is satisfied, as FIRST(eS) ∩ FIRST(ε) = {e} ∩ {ε} = Φ. But here due to 'ε' in FIRST, we have to check for rule 2. FIRST(eS) ∩ FOLLOW(S1) = {e} ∩ {e, $} ≠ Φ. Hence rule 2 fails in this production rule. Therefore there will be multiple entries in the parsing table, hence the grammar is ambiguous and not LL(1).
Most Upvoted Answer
Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,...
Explanation:
The given grammar is not LL(1) because it is ambiguous.
Ambiguous Grammar:
An ambiguous grammar is a context-free grammar that generates a language where some strings in the language have more than one leftmost derivation or more than one parse tree.
LL(1) Grammar:
An LL(1) grammar is a context-free grammar in which no two distinct productions have the same left side and the same first terminal symbol on the right side. It means that for any non-terminal symbol, there should be only one production rule that can be applied based on the next input symbol.
Analysis of the Given Grammar:
The given grammar has the following set of rules:
1. S -- iCtSS1
2. S -- aS1
3. S1 -- eS
4. C -- b
Conflict in the Grammar:
The conflict arises in the parsing table for the non-terminal symbol S. The first set of S contains both 'i' and 'a', which are the first terminals of the two production rules for S. In LL(1) grammar, each non-terminal should have a unique first terminal symbol.
Parsing Table:
To construct the LL(1) parsing table, we need to find the first and follow sets for each non-terminal and terminal symbol.
The first set of S:
First(S) = {i, a}
The first set of S1:
First(S1) = {e}
The first set of C:
First(C) = {b}
The follow set of S:
Follow(S) = {t}
Conflict in the Parsing Table:
Using the above first and follow sets, we can construct the parsing table. However, we can observe that for the non-terminal symbol S, there is a conflict in the parsing table. Both 'i' and 'a' are in the first set of S, which violates the condition of LL(1) grammar.
Ambiguity in the Grammar:
The ambiguity in the grammar arises because there is more than one valid leftmost derivation or parse tree for some strings in the language generated by the grammar. In this case, the string 'iat' can be derived in two ways:
1. S -> iCtSS1 -> iCtaS1 -> iatS1 -> iat (using the production rule S -- iCtSS1 followed by S1 -- aS1)
2. S -> aS1 -> iatS1 -> iat (using the production rule S -- aS1)
Conclusion:
Since the given grammar is ambiguous, it cannot be LL(1). Therefore, the correct answer is option 'C' - it is ambiguous.
The given grammar is not LL(1) because it is ambiguous.
Ambiguous Grammar:
An ambiguous grammar is a context-free grammar that generates a language where some strings in the language have more than one leftmost derivation or more than one parse tree.
LL(1) Grammar:
An LL(1) grammar is a context-free grammar in which no two distinct productions have the same left side and the same first terminal symbol on the right side. It means that for any non-terminal symbol, there should be only one production rule that can be applied based on the next input symbol.
Analysis of the Given Grammar:
The given grammar has the following set of rules:
1. S -- iCtSS1
2. S -- aS1
3. S1 -- eS
4. C -- b
Conflict in the Grammar:
The conflict arises in the parsing table for the non-terminal symbol S. The first set of S contains both 'i' and 'a', which are the first terminals of the two production rules for S. In LL(1) grammar, each non-terminal should have a unique first terminal symbol.
Parsing Table:
To construct the LL(1) parsing table, we need to find the first and follow sets for each non-terminal and terminal symbol.
The first set of S:
First(S) = {i, a}
The first set of S1:
First(S1) = {e}
The first set of C:
First(C) = {b}
The follow set of S:
Follow(S) = {t}
Conflict in the Parsing Table:
Using the above first and follow sets, we can construct the parsing table. However, we can observe that for the non-terminal symbol S, there is a conflict in the parsing table. Both 'i' and 'a' are in the first set of S, which violates the condition of LL(1) grammar.
Ambiguity in the Grammar:
The ambiguity in the grammar arises because there is more than one valid leftmost derivation or parse tree for some strings in the language generated by the grammar. In this case, the string 'iat' can be derived in two ways:
1. S -> iCtSS1 -> iCtaS1 -> iatS1 -> iat (using the production rule S -- iCtSS1 followed by S1 -- aS1)
2. S -> aS1 -> iatS1 -> iat (using the production rule S -- aS1)
Conclusion:
Since the given grammar is ambiguous, it cannot be LL(1). Therefore, the correct answer is option 'C' - it is ambiguous.
Attention Computer Science Engineering (CSE) Students!
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Similar Computer Science Engineering (CSE) Doubts
Top Courses for Computer Science Engineering (CSE)View all
Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer?
Question Description
Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer?.
Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer?.
Solutions for Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE).
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer?, a detailed solution for Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer? has been provided alongside types of Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Consider the grammar with non-terminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:S --> iCtSS1|aS1 --> eS|ϵC --> bThe grammar is NOT LL(1) because:a)it is left recursiveb)it is right recursivec)it is ambiguousd)It is not context-freeCorrect answer is option 'C'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup